
void swap(double *s, int idx1, int idx2) {
    double tmp = s[idx1];
    s[idx1] = s[idx2];
    s[idx2] = tmp;
}
void push(double *s, int *size, double val) {
    int son = *size;
    int dad = (son - 1) / 2;
    s[son] = val;
    while (son) {
        if (s[son] <= s[dad]) { break; }
        swap(s, son, dad);
        son = dad;
        dad = (son - 1) / 2;
    }
    (*size)++;
}
void update(double *s, int size) {
    s[0] /= 2.0;
    int dad = 0;
    int son = 2 * dad + 1;
    while (son < size) {
        if (son+1 < size && s[son+1] > s[son]) { son++; }
        if (s[dad] >= s[son]) { break; }
        swap(s, son, dad);
        dad = son;
        son = 2 * dad + 1;
    }
}
int halveArray(int* nums, int numsSize){
    double s[numsSize];
    int size = 0;
    double half = 0.0, sum = 0.0;
    for (int i = 0; i < numsSize; i++) {
        push(s, &size, (double)nums[i]);
        half += (double)nums[i];
    }
    half /= 2.0;
    int ans = 0;
    while (1) {
        ans++;
        sum += s[0] / 2.0;
        if (sum >= half) {
            break;
        }
        update(s, size);
    }
    return ans;
}

